//给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。 
//
// 
//
// 示例 1: 
//
// 
//输入: s1 = "sea", s2 = "eat"
//输出: 231
//解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
//在 "eat" 中删除 "t" 并将 116 加入总和。
//结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
// 
//
// 示例 2: 
//
// 
//输入: s1 = "delete", s2 = "leet"
//输出: 403
//解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
//将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
//结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
//如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
// 
//
// 
//
// 提示: 
//
// 
// 0 <= s1.length, s2.length <= 1000 
// s1 和 s2 由小写英文字母组成 
// 
// Related Topics字符串 | 动态规划 
//
// 👍 287, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class MinimumAsciiDeleteSumForTwoStrings {
    public static void main(String[] args) {
        Solution solution = new MinimumAsciiDeleteSumForTwoStrings().new Solution();
        solution.minimumDeleteSum("delete", "leet");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 公共子序列的变种，和583一致
        // 自底向上计算
        public int minimumDeleteSum(String s1, String s2) {
            int m = s1.length(), n = s2.length();
            // 先计算出所有ASCLL再相减
            int s1AscllSum = 0, s2AscllSum = 0;
            for (int i = 0; i < m; i++) {
                s1AscllSum += s1.charAt(i);
            }

            for (int i = 0; i < n; i++) {
                s2AscllSum += s2.charAt(i);
            }

            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        dp[i][j] = s1.charAt(i - 1) + dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }

            return (s1AscllSum - dp[m][n]) + (s2AscllSum - dp[m][n]);
        }

        // 自顶向下计算参照：https://leetcode.cn/problems/delete-operation-for-two-strings/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
